Flip-flops and latches are widely used in computers and other electronic devices, for example, as sampling, counting and storage elements. A number of flip-flop types have been developed, such as D-type flip-flops (“data”), R-S latches (“reset and set”), J-K flip-flops (having J and K inputs) and T flip-flops (having only one input). A D-type flip-flop, for example, is a clocked flip-flop whose output is delayed by one clock pulse.
A conventional R-S latch 100 is shown in FIG. 1A. As in FIG. 1A, the R-S latch 100 is comprised of two NOR gates 110 and 120. The outputs of the two NOR gates 110, 120 are cross-connected to a respective input of the opposite NOR gate. Thus, NOR gate 110 receives the output of NOR gate 120 and a reset 30 signal, R, as inputs. Likewise, NOR gate 120 receives the output of NOR gate 110 and the set signal, S, as inputs.
More recently, the simple latches shown in FIG. 1A have been replaced by edge-triggered flip-flops, such as the D-type flip-flop 150 is shown in FIG. 1B. Such D-type flip-flops are often used to detect the logic state of an asynchronous digital signal having an unpredictable timing relative to the clock signal. A rising signal is applied to the clock input, CLK, of the flip-flop 150, while a digital logic level of the asynchronous signal to be detected is directed to the D input. The detected signal is then produced on the Q output line. As long as the clock does not rise again, the output Q does not change. Thereafter, the flip-flop 150 simply changes state to the value on the D input whenever the CLK signal rises (so long as the reset signal is tied permanently to ground).
The latches 100 shown in FIG. 1A are susceptible to meta-stability. For a detailed discussion of meta-stability, see, for example, Application Note, A Meta-Stability Primer, AN219, Philips Semiconductors (Nov. 15, 1989), incorporated by reference herein. Generally, meta-stability can occur when both inputs to a latch 100 are set at a high logic value (“11”), and are then reset to a low logic value (“00”) Under these conditions, the latch outputs can oscillate unpredictably in a statistically known manner. In theory, the latch 100 can oscillate indefinitely. In practice, however, the latch 100 will randomly shift and arrive at a random output value of either logic low or high. Typically, these meta-stable values are subsequently detected by other circuitry in a given application and can be interpreted as different logic level states or assume an intermediate state that can be misinterpreted by other logic gates.
In addition, the edge-triggered flip-flop 150 shown in FIG. 1B can become meta-stable when the setup or hold times of the flip-flop are violated. Edge-triggered flip-flops 150 are susceptible to meta-stability because inside every edge-triggered flip-flop 150 there is a latch 100 being fed by the edge detection circuitry. If the setup or hold times are violated then the internal latch 100 will observe inputs that can trigger the meta-stable state.
Many applications and electronic devices require random numbers, including games of chance, such as poker, roulette, and slot machines. In particular, numerous cryptographic algorithms and protocols depend on a non-predictable source of random numbers to implement secure electronic communications and the like. A random number generator should generate every possible permutation in the designated range of numbers. In addition, the random number generator should not be biased and should generate any given number with the same probability as any other number. Moreover, the random number generator should generate random numbers that cannot be predicted, irrespective of the size of the collection of previous results. Thus, the random numbers should be completely unpredictable and non-susceptible to outside influences.
U.S. patent application Ser. No. 09/519,549, filed Mar. 6, 2000, entitled “Method and Apparatus for Generating Random Numbers Using Flip-Flop Meta-Stability,” discloses a method and apparatus for generating random numbers using the meta-stable behavior of flip-flops. A flip-flop is clocked with an input that deliberately violates the setup or hold times (or both) of the flip-flop to ensure meta-stable behavior. A bit is collected whenever there is an error. If meta-stability occurs more frequently with one binary value (either zero or one) for a given class of flip-flops, an even random number distribution is obtained by “marking” half of the zeroes as “ones” and the other half of the zeroes as “zeroes.” In addition, half of the ones are marked as “ones” and the other half are marked as “zeroes”.
Marking input bits in this manner theoretically provides an even distribution of random output bits. While meta-stability occurs on a random basis, it has been found that the duration and occurrence of meta-stability is affected by noise. Thus, if the noise is correlated to the marking signal, then the output of the random number generator will not be random. A need therefore exists for a method and apparatus for generating random numbers using meta-stability that is not influenced by noise or other outside forces. A further need exists for a method and apparatus for generating random numbers using meta-stability that that uses a marking signal that is uncorrelated with a high probability to any noise in the system.